package top.kiterunner.learning.moon_test;

/**
 * AdorynZhao in Tencent-UESTC.
 * Source Code Created on 2017/7/13.
 */
public class QuickSort {

    public static void main (String[] args) {
        int[] num = {2,9,3,5,8,1};
        sort(num, 0, num.length-1);
        for(int i : num)
            System.out.print(i);
    }

    public static void sort (int[] num, int start, int end) {
        if(num == null || num.length == 0) return;
        if(start >= end) return;
        int mid = partition(num, start, end);
        sort(num, start, mid-1);
        sort(num, mid+1, end);
    }

    public static int partition(int[] num, int start, int end) {
        int lo = start;
        int hi = end+1;
        int value = num[start];
        while(true) {
            while(num[++lo] < value) if(lo >= end) break;
            while(num[--hi] > value) if(hi <= start) break;
            if( lo >= hi) break;
            exch(num, lo, hi);
        }
        exch(num, start, hi);
        return hi;
    }

    public static void exch(int[] num, int i, int j){
        int trf = num[i];
        num[i] = num[j];
        num[j] = trf;
    }
}
